UVa/12323 - Inspecting Radars/12323.cpp

   1 // Time Limit Exceeded
   2 using namespace std;
   3 #include <algorithm>
   4 #include <iostream>
   5 #include <iterator>
   6 #include <numeric>
   7 #include <sstream>
   8 #include <fstream>
   9 #include <cassert>
  10 #include <climits>
  11 #include <cstdlib>
  12 #include <cstring>
  13 #include <string>
  14 #include <cstdio>
  15 #include <vector>
  16 #include <cmath>
  17 #include <queue>
  18 #include <deque>
  19 #include <stack>
  20 #include <list>
  21 #include <map>
  22 #include <set>
  23
  24 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
  25 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  26 #define D(x) cout << #x " is " << x << endl
  27
  28 typedef pair<int, int> point;
  29
  30 const int MAXN = 10000;
  31 const int MAXR = 101;
  32
  33 point points[2 * MAXN];
  34 int height[MAXR], N, R;
  35
  36 void solve(int distance, int angle) {
  37     int ans = 0;
  38     int i = 0, j = 0;
  39     for (int r = 0; r <= R; ++r) {
  40         height[r] = 0;
  41     }
  42     while (i < N) {
  43         while (j < N and points[i].first + angle >= points[j].first) {
  44             height[points[j].second]++;
  45             j++;
  46         }
  47         // from [i, j) they are correctly separated by angle
  48         // printf("i = %d, j = %d, angle = %d\n", i, j, angle);
  49         // printf("  "); For(k, i, j) printf("<%d, %d> ", points[k].first, points[k].second); puts("");
  50         // For(r, 0, MAXR) {
  51         //     if (height[r] > 0) {
  52         //         printf("height[%d] = %d\n", r, height[r]);
  53         //     }
  54         // }
  55
  56         int sum = 0;
  57         int p = 0, q = 0;
  58         while (p <= R) {
  59             while (q <= R and p + distance > q) {
  60                 sum += height[q];
  61                 q++;
  62             }
  63             // if (sum > 0) {
  64             //     printf("possible option from p=%d to q=%d with sum = %d\n", p, q, sum);
  65             // }
  66             ans = max(ans, sum);
  67             sum -= height[p++];
  68             while (p <= R and height[p] == 0) p++;
  69         }
  70
  71         height[points[i++].second]--;
  72     }
  73     printf("%d\n", ans);
  74 }
  75
  76 int main(){
  77     while (scanf("%d %d", &N, &R) == 2) {
  78         if (N == 0 and R == 0) break;
  79         for (int i = 0; i < N; ++i) {
  80             int distance, angle;
  81             scanf("%d %d", &distance, &angle);
  82             points[2*i] = make_pair(angle, distance);
  83             points[2*i + 1] = make_pair(angle + 360, distance);
  84         }
  85         N *= 2;
  86         sort(points, points + N);
  87
  88         int E;
  89         scanf("%d", &E);
  90         while (E--) {
  91             int distance, angle;
  92             scanf("%d %d", &distance, &angle);
  93             solve(distance, angle);
  94         }
  95     }
  96     return 0;
  97 }